GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Deque</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Deque</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Ein Deque (Double-ended queue, sprich: „Deck“) bezeichnet eine <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> der <a href="Informatik" title="Informatik">Informatik</a>.

Hierbei handelt es sich um eine <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> ähnlich der <a href="Warteschlange_(Datenstruktur)" title="Warteschlange (Datenstruktur)">Warteschlange</a> oder des <a href="Stapelspeicher" title="Stapelspeicher">Stapelspeichers</a>. Es kombiniert die Eigenschaften beider <a href="Datentyp" title="Datentyp">Datentypen</a>. Der Unterschied besteht darin, dass die Daten an beiden Enden gelesen, eingefügt oder entfernt werden können.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

Die Operationen eines Deque, die in den <a href="Programmbibliothek" title="Programmbibliothek">Programmbibliotheken</a> verschiedener <a href="Programmiersprache" title="Programmiersprache">Programmiersprachen</a> nicht einheitlich benannt sind:

<ul><li>push und pop für das Einfügen oder Entnehmen eines Elements am hinteren Ende der Deque.</li>

<li>put und get für das Einfügen oder Entnehmen am vorderen Ende der Deque.</li>

<li>first und last für das Lesen des ersten oder letzten Elementes, ohne es zu entfernen.</li></ul>

Technisch wird ein Deque als ein Array von Pointern auf einzelne Chunks mit jeweils gleicher Größe realisiert. Damit ist gesichert, dass der wahlfreie Zugriff mit konstanter Zeit erfolgen kann, was der C++-Standard verlangt. Durch die jeweils gleiche Größe der Chunks lässt sich deren Position für den indizierten Zugriff (Operator []) schnell berechnen. Dies wäre mit einer verketteten Liste nicht möglich. Dadurch, dass jeweils mehrere Elemente in einen Chunk passen ist das Einfügen und Entfernen an den Enden schneller als bei einer Liste da für so viele Elemente die in einen Chunk passen genau eine Speicherallokation erforderlich ist.

Deques sind Sequenzcontainer mit dynamischen Größen, die an beiden Enden (entweder vorne oder hinten) erweitert oder verkleinert werden können. Bestimmte <a href="Programmbibliothek" title="Programmbibliothek">Programmbibliotheken</a> können Deques auf unterschiedliche Weise implementieren, im Allgemeinen als eine Form eines dynamischen <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Arrays</a>. In jedem Fall ermöglichen sie jedoch den direkten Zugriff auf die einzelnen Elemente über Iteratoren mit wahlfreiem Zugriff, wobei der Speicher automatisch verwaltet wird, indem der Container nach Bedarf erweitert und verkleinert wird.

Daher bieten sie eine ähnliche Funktionalität wie <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Arrays</a>, jedoch mit effizienter Einfügung und Löschung von Elementen auch am Anfang der Sequenz und nicht nur am Ende. Im Gegensatz zu Arrays wird jedoch nicht garantiert, dass Deques alle ihre Elemente an zusammenhängenden <a href="Speicheradresse" title="Speicheradresse">Speicheradressen</a> speichern: Der Zugriff auf Elemente in einer Deque durch Versetzen eines Zeigers auf ein anderes Element führt zu undefiniertem Verhalten. Sowohl dynamischen Arrays als auch Deques bieten eine sehr ähnliche Schnittstelle und können für ähnliche Zwecke verwendet werden, aber intern funktionieren beide auf ganz unterschiedliche Weise: Während Vektoren ein einzelnes Array verwenden, das gelegentlich für das Wachstum neu zugewiesen werden muss, können die Elemente eines Deque auf verschiedene <a href="Speicherblock" class="mw-redirect" title="Speicherblock">Speicherblöcke</a> verstreut werden, wobei der Container die erforderlichen Informationen intern speichert, um in konstanter <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> und mit einer einheitlichen sequentiellen Schnittstelle (über <a href="Iterator" title="Iterator">Iteratoren</a>) direkten Zugriff auf eines seiner Elemente zu ermöglichen.

Daher sind Deques intern etwas komplexer, aber dies ermöglicht es ihnen, unter bestimmten Umständen effizienter zu wachsen, insbesondere bei sehr langen Sequenzen, bei denen Neuzuweisungen teurer werden. Bei <a href="Operation_(Informatik)" title="Operation (Informatik)">Operationen</a>, bei denen Elemente häufig an anderen Positionen als am Anfang oder am Ende eingefügt oder entfernt werden, sind Deques schlechter und weisen weniger konsistente <a href="Iterator_(Entwurfsmuster)" title="Iterator (Entwurfsmuster)">Iteratoren</a> und <a href="Referenz_(Programmierung)" title="Referenz (Programmierung)">Referenzen</a> auf als <a href="Liste_(Datenstruktur)" title="Liste (Datenstruktur)">Listen</a>.<a href="#cite_note-1">[1]</a>

In der Praxis verwendet man die Deque unter anderem zur Implementierung von <a href="Nichtdeterministischer_endlicher_Automat" title="Nichtdeterministischer endlicher Automat">nichtdeterministischen endlichen Automaten</a> und zur Textsuche mittels <a href="Regul%C3%A4rer_Ausdruck" title="Regulärer Ausdruck">regulärer Ausdrücke</a> (<a href="Pattern_Matching" title="Pattern Matching">Pattern-Matching</a>-<a href="Algorithmus" title="Algorithmus">Algorithmus</a>).

<div class="mw-heading mw-heading2"><h2 id="Programmierung">Programmierung</h2></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C%2B%2B" title="C++">C++</a> mit Spielkarten zeigt die Verwendung der <a href="Klasse_(Objektorientierung)" title="Klasse (Objektorientierung)">Klasse</a> deque der <a href="C%2B%2B-Standardbibliothek" title="C++-Standardbibliothek">C++-Standardbibliothek</a> (siehe auch <a href="Template_(C%2B%2B)#Klassen-Templates" title="Template (C++)">Template (C++) - Klassen-Templates</a>). Bei der Ausführung des Programms wird die Methode main verwendet.<a href="#cite_note-2">[2]</a><div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre>#include <deque> // Bindet den Datentyp deque in das Programm ein

#include <iostream>

using namespace std;

int main()

{

deque<string> myDeque; // Deklariert ein Deque mit dem Elementtyp string

// Fügt dem Deque 3 Elemente vom Typ string am Ende hinzu

myDeque.push_back("Kreuz Bube");

myDeque.push_back("Herz Dame");

myDeque.push_back("Karo König");

cout << "Die Länge des Deque ist "

<< myDeque.size() << endl; // Ausgabe Anzahl der Elemente

string card = myDeque.front(); // Weist das Element am Anfang ("Kreuz Bube") der Variablen card zu

cout << "Die Karte am Anfang der Deque ist: "

<< card << endl; // Ausgabe

card = myDeque.back(); // Weist das Element am Ende ("Karo König") der Variablen card zu

cout << "Die Karte am Ende der Deque ist: "

<< card << endl; // Ausgabe der Karte

cout << toString(myDeque) << endl; // Ausgabe: (Kreuz Bube, Herz Dame, Karo König)

myDeque.push_front("Kreuz 10"); // Fügt 1 Element am Anfang des Deque ein

cout << "Die Länge des Deque ist "

<< myDeque.size() << endl; // Ausgabe Anzahl der Elemente

cout << toString(myDeque) << endl; // Ausgabe: (Kreuz 10, Kreuz Bube, Herz Dame, Karo König)

myDeque.pop_back(); // Entfernt das Element am Ende

cout << toString(myDeque) << endl; // Ausgabe: (Kreuz 10, Kreuz Bube, Herz Dame)

myDeque.push_back("Karo Ass"); // Fügt dem Deque 1 Element am Ende hinzu

cout << toString(myDeque) << endl; // Ausgabe auf der Konsole: (Kreuz 10, Kreuz Bube, Herz Dame, Karo Ass)

myDeque.pop_front(); // Entfernt das Element am Anfang

cout << toString(myDeque) << endl; // Ausgabe: (Kreuz Bube, Herz Dame, Karo Ass)

}

</pre></div>

Für die Ausgabe des Deque wird folgende <a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methode</a> verwendet:

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre>// Diese Methode gibt das Deque in der Form (A, B, C, ...) als Text zurück.

string toString(deque<string> & aDeque)

{

if (aDeque.empty())

return "()";

string text = "(";

for (size_t i = 0; i < aDeque.size() - 1; i++)

text += aDeque.at(i) + ", ";

text += aDeque.at(aDeque.size() - 1) + ")";

return text;

}

</pre></div>

Für die Programmierung von <a href="Kartenspiel" title="Kartenspiel">Kartenspielen</a> und <a href="Gesellschaftsspiel" title="Gesellschaftsspiel">Gesellschaftsspielen</a> mit Stapeln, bei denen während des Spiels Karten auf einen Stapel gelegt oder von einem Stapel gezogen wird, sind stattdessen Stacks geeignet (siehe <a href="Stapelspeicher#Beispiel_mit_Spielkarten" title="Stapelspeicher">Stapelspeicher - Beispiel mit Spielkarten</a>).

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Warteschlange_(Datenstruktur)" title="Warteschlange (Datenstruktur)">Warteschlange (Datenstruktur)</a></li>

<li><a href="Stapelspeicher" title="Stapelspeicher">Stapelspeicher</a></li>

<li><a href="Doppelt_verkettete_Liste" class="mw-redirect" title="Doppelt verkettete Liste">Doppelt verkettete Liste</a></li>

<li><a href="Heap_(Datenstruktur)" title="Heap (Datenstruktur)">Heap (Datenstruktur)</a></li>

<li><a href="Iterator" title="Iterator">Iterator</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

www.geeksforgeeks.org: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/implementation-deque-using-doubly-linked-list/">Implementation of Deque using doubly linked list</a>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> www.cplusplus.com: <a rel="nofollow" class="external text" href="https://www.cplusplus.com/reference/deque/deque/">deque</a>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Microsoft Docs: <a rel="nofollow" class="external text" href="https://docs.microsoft.com/en-us/cpp/standard-library/deque-class?view=msvc-160">deque Class</a>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-08-25" href="https://de.wikipedia.org/wiki/?title=Deque&oldid=248044485">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>